﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Csharpzuoye
{
    //用泛型改造二分查找、堆栈和双向链表 
    //用泛型改造“取数组中最大值”（提示：IComparable）

    public class Search<T> where T : IComparable<T>
    {
        //实现二分查找，方法名BinarySeek(int[] numbers, int target)：
        //传入一个有序（从大到小/从小到大）数组和数组中要查找的元素
        //如果找到，返回该元素所在的下标；否则，返回-1
        public static T BinarySeek(T[] numbers, T target)
        {
            //int[] numbers = { 1, 3, 5, 7, 9 };
            //int target = 7;
            int left = 0, right = numbers.Length - 1, middle;
            while (left < right)
            {
                middle = (left + right) / 2;
                if (target.CompareTo(numbers[middle]) < 0)
                {
                    right = middle - 1;
                }
                else if (target.CompareTo(numbers[middle]) > 0)
                {
                    left = middle + 1;
                }
                else //if(target == numbers[middle])
                {
                    return numbers[middle];
                }
            }
            return default(T);
        }

    }

    public class MimicStack<T>
    {
        //自己实现一个模拟栈（MimicStack）类，入栈出栈数据均为int类型，包含如下功能：   压入数据top指针动 bottom不动
        //1.出栈Pop()，弹出栈顶数据            //栈的作业会用到索引器里面构造函数确定长度
        //2.入栈Push()，可以一次性压入多个数据  当方法的参数是数组的时候，我们可以在数组类型前面加一个关键字params
        //3.出/入栈检查，
        //  1.)如果压入的数据已超过栈的深度（最大容量），提示“栈溢出”stack overflow
        //  2.)如果已弹出所有数据，提示“栈已空”The stack is empty
        private T[] arrays;
        private int top = 0;
        public MimicStack(int length)
        {
            arrays = new T[length];
        }
        public void Push(T element)//截断式编程
        {
            if (top > arrays.Length)
            {
                Console.WriteLine("stack overflow");
            }
            else
            {
                arrays[top] = element;//元素放进栈顶指针指向的位置
                top++;
            }
        }
        public void Push(params T[] elements)//重载
        {
            for (int i = 0; i < elements.Length; i++)
            {
                Push(elements[i]);
            }
        }
        public void Pop(out bool succeed)
        {
            if (top == 0)
            {
                succeed = false;
                Console.WriteLine("The stack is empty");
            }
            else
            {
                top--;
                succeed = true;
                Console.WriteLine(arrays[top]);

            }
        }
        public bool Pop()
        {
            if (top == 0)
            {
                Console.WriteLine("The stack is empty");
                return false;
            }
            else
            {
                top--;
                Console.WriteLine(arrays[top]);
                return true;
            }

        }

    }

    public class Value<T> where T : IComparable<T>
    {
        public static T GetMaxValue(T[] numbers)
        {
            T max = default(T);
            for (int i = 0; i < numbers.Length; i++)
            {
                if (numbers[i].CompareTo(max) > 0)
                {
                    max = numbers[i];
                }
            }
            return max;
        }
    }

}
